package link;

import java.util.List;

/**
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 */
public class leetCode148_sortList {

    public ListNode sortList(ListNode head) {
        return sort(head,null);
    }

    public ListNode sort(ListNode head,ListNode tail){
        if(head == null) return null;
        if(head.next == tail){
            head.next = null;
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != tail && fast.next != tail){
            fast = fast.next.next;
            slow  = slow.next;
        }
        ListNode mid = slow;
        ListNode left = sort(head, mid);
        ListNode right = sort(mid, tail);
        return merge(left,right);


    }

    public ListNode merge(ListNode l1,ListNode l2){
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode res = new ListNode(-1);
        ListNode tmp = res;
        while (l1 != null && l2 != null){
            if(l1.val < l2.val){
                tmp.next = l1;
                l1 = l1.next;
            }else{
                tmp.next = l2;
                l2 = l2.next;
            }
            tmp = tmp.next;
        }
        tmp.next = l1 == null?l2:l1;
        return res.next;
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {

        }
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

}
